In large-scale machine learning, recent works have studied the effects of compressing gradients in stochastic optimization in order to alleviate the communication bottleneck. These works have collectively revealed that stochastic gradient descent (SGD) is robust to structured perturbations such as quantization, sparsification, and delays. Perhaps surprisingly, despite the surge of interest in large-scale, multi-agent reinforcement learning, almost nothing is known about the analogous question: Are common reinforcement learning (RL) algorithms also robust to similar perturbations? In this paper, we investigate this question by studying a variant of the classical temporal difference (TD) learning algorithm with a perturbed update direction, where a general compression operator is used to model the perturbation. Our main technical contribution is to show that compressed TD algorithms, coupled with an error-feedback mechanism used widely in optimization, exhibit the same non-asymptotic theoretical guarantees as their SGD counterparts. We then extend our results significantly to nonlinear stochastic approximation algorithms and multi-agent settings. In particular, we prove that for multi-agent TD learning, one can achieve linear convergence speedups in the number of agents while communicating just $\tilde{O}(1)$ bits per agent at each time step. Our work is the first to provide finite-time results in RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling. Our analysis hinges on studying the drift of a novel Lyapunov function that captures the dynamics of a memory variable introduced by error feedback.

Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions.

域的概括（DG）通过利用来自多个相关分布或域的标记培训数据在看不见的测试分布上表现良好的预测因子。为了实现这一目标，标准公式优化了所有可能域的最差性能。但是，由于最糟糕的转变在实践中的转变极不可能，这通常会导致过度保守的解决方案。实际上，最近的一项研究发现，没有DG算法在平均性能方面优于经验风险最小化。在这项工作中，我们认为DG既不是最坏的问题，也不是一个普通的问题，而是概率问题。为此，我们为DG提出了一个概率框架，我们称之为可能的域概括，其中我们的关键想法是在训练期间看到的分配变化应在测试时告诉我们可能的变化。为了实现这一目标，我们将培训和测试域明确关联为从同一基础元分布中获取的，并提出了一个新的优化问题 - 分数风险最小化（QRM） - 要求该预测因子以很高的概率概括。然后，我们证明了QRM：（i）产生的预测因子，这些预测因素将具有所需概率的新域（给定足够多的域和样本）； （ii）随着概括的所需概率接近一个，恢复因果预测因子。在我们的实验中，我们引入了针对DG的更全面的以分位数评估协议，并表明我们的算法在真实和合成数据上的最先进基准都优于最先进的基准。

已经为图形生成模型提出了广泛的模型，需要采用有效的方法来评估其质量。到目前为止，大多数技术都使用基于子图计数的传统指标或随机初始化的图形神经网络（GNN）的表示。我们建议使用对比训练的GNN而不是随机GNN的表示形式，并表明这给出了更可靠的评估指标。但是，传统方法和基于GNN的方法都没有主导另一方：我们举例说明每种方法无法区分的示例。我们证明了图形子结构网络（GSN），以一种结合两种方法的方式，可以更好地区分图形数据集之间的距离。

我们考虑了认证深神经网络对现实分布变化的鲁棒性的问题。为此，我们通过提出一个新型的神经符号验证框架来弥合手工制作的规格和现实部署设置之间的差距模型。这种环境引起的一个独特的挑战是，现有的验证者不能紧密地近似sigmoid激活，这对于许多最新的生成模型至关重要。为了应对这一挑战，我们提出了一个通用的元算象来处理乙状结肠激活，该乙状结激素利用反示例引导的抽象细化的经典概念。关键思想是“懒惰地”完善Sigmoid函数的抽象，以排除先前抽象中发现的虚假反示例，从而确保验证过程中的进展，同时保持状态空间较小。 MNIST和CIFAR-10数据集的实验表明，我们的框架在一系列具有挑战性的分配变化方面大大优于现有方法。

Fokker-Planck方程（FPE）是控制IT \^o过程密度演变的部分微分方程，并且对统计物理学和机器学习的文献非常重要。 FPE可以被视为连续性方程，其中密度的变化完全由时间变化的速度场决定。重要的是，此速度场也取决于当前密度函数。结果，可以证明地面真相速度字段是固定点方程的解决方案，即我们称之为自洽的属性。在本文中，我们利用这一概念来设计假设速度字段的潜在功能，并证明，如果在训练过程中这样的功能减少到零，则假设速度场产生的密度轨迹会收敛到解决方案转化为解决方案。 Wasserstein-2的FPE。所提出的潜在函数可与基于神经网络的参数化相提并论，因为可以有效地计算相对于参数的随机梯度。一旦训练了一个参数化模型，例如神经普通微分方程，我们就可以生成FPE的整个轨迹。

在本文中，我们通过图形函数的关键代数条件（称为\ textIt {置换兼容性}）完全回答上述问题，该函数将图形和图形的特征​​与功能约束相关联。我们证明：（i）GNN作为图形函数必然是兼容的； （ii）相反，当限制具有不同节点特征的输入图上时，任何置换兼容函数都可以由GNN生成； （iii）对于任意节点特征（不一定是不同），一个简单的功能增强方案足以生成GNN置换兼容函数； （iv）可以通过仅检查二次功能约束，而不是对所有排列的详尽搜索来验证置换兼容性； （v）GNN可以生成\ textIt {any}图形函数，一旦我们以节点身份增强节点特征，从而超越了图同构和置换兼容性。上面的表征铺平了正式研究GNN和其他算法程序之间复杂联系的路径。例如，我们的表征意味着许多自然图问题，例如最小值值，最大流量值，最大值尺寸和最短路径，可以使用简单的功能增强来生成GNN。相比之下，每当GNN无法生成具有相同特征的置换函数时，著名的Weisfeiler-Lehman图形测试就会失败。我们分析的核心是一种新的表示定理，它标识了GNN的基础函数。这使我们能够将目标图函数的属性转化为GNN聚合函数的属性。

机器学习的许多成功都是基于最大程度地减少平均损失函数的基础。但是，众所周知，这种范式遭受了鲁棒性问题的影响，阻碍了其在安全 - 关键领域中的适用性。这些问题通常是通过针对最坏情况的数据扰动来解决的，该技术被称为对抗性训练。尽管经验上有效，但对抗性训练可能过于保守，从而导致名义性能和稳健性之间的不利权衡。为此，在本文中，我们提出了一个称为概率鲁棒性的框架，该框架弥合了准确但脆弱的平均情况和坚固而保守的最坏情况之间的差距，这是通过对最多而不是对所有扰动的实施强大的。从理论的角度来看，该框架克服了最差案例学习和平均案例学习的性能与样本复杂性之间的权衡。从实际的角度来看，我们提出了一种基于风险感知优化的新算法，该算法有效地平衡了平均和最差的案例性能，而相对于对抗性训练，计算成本较低。我们对MNIST，CIFAR-10和SVHN的结果说明了该框架在从平均值到最差的鲁棒性方面的优势。

成功的深度学习模型往往涉及培训具有比训练样本数量更多的参数的神经网络架构。近年来已经广泛研究了这种超分子化的模型，并且通过双下降现象和通过优化景观的结构特性，从统计的角度和计算视角都建立了过分统计化的优点。尽管在过上分层的制度中深入学习架构的显着成功，但也众所周知，这些模型对其投入中的小对抗扰动感到高度脆弱。即使在普遍培训的情况下，它们在扰动输入（鲁棒泛化）上的性能也会比良性输入（标准概括）的最佳可达到的性能更糟糕。因此，必须了解如何从根本上影响稳健性的情况下如何影响鲁棒性。在本文中，我们将通过专注于随机特征回归模型（具有随机第一层权重的两层神经网络）来提供超分度化对鲁棒性的作用的精确表征。我们考虑一个制度，其中样本量，输入维度和参数的数量彼此成比例地生长，并且当模型发生前列地训练时，可以为鲁棒泛化误差导出渐近精确的公式。我们的发达理论揭示了过分统计化对鲁棒性的非竞争效果，表明对于普遍训练的随机特征模型，高度公正化可能会损害鲁棒泛化。

在机器学习，游戏理论和控制理论中解决各种应用，极限优化已经是中心。因此，目前的文献主要集中于研究连续结构域中的这些问题，例如，凸凹minalax优化现在在很大程度上被理解。然而，最小的问题远远超出连续域以混合连续离散域或甚至完全离散域。在本文中，我们研究了混合连续离散的最小问题，其中最小化在属于欧几里德空间的连续变量上，最大化是在给定地面集的子集上。我们介绍了凸子蒙皮最小新的类问题，其中物镜相对于连续变量和子模块相对于离散变量凸出。尽管这些问题在机器学习应用中经常出现，但对于如何从算法和理论观点来解决它们的知之甚少。对于此类问题，我们首先表明获得鞍点难以达到任何近似，因此引入了（近）最优性的新概念。然后，我们提供了若干算法程序，用于解决凸且单调 - 子模块硬币问题，并根据我们最佳的概念来表征其收敛率，计算复杂性和最终解决方案的质量。我们所提出的算法迭代并组合离散和连续优化的工具。最后，我们提供了数字实验，以展示我们所用方法的有效性。